House Robber II

LeetCode 213 | Difficulty: Medium

Medium

Problem Description

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return *the maximum amount of money you can rob tonight without alerting the police*.

Example 1:

Input: nums = [2,3,2]
Output: 3
Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses.

Example 2:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 3:

Input: nums = [1,2,3]
Output: 3

Constraints:

- `1 <= nums.length <= 100`

- `0 <= nums[i] <= 1000`

Topics: Array, Dynamic Programming

---

Approach

Dynamic Programming

Break the problem into overlapping subproblems. Define a state (what information do you need?), a recurrence (how does state[i] depend on smaller states?), and a base case. Consider both top-down (memoization) and bottom-up (tabulation) approaches.

When to use

Optimal substructure + overlapping subproblems (counting ways, min/max cost, feasibility).

---

Solutions

Solution 1: C# (Best: 141 ms)

Metric	Value
Runtime	141 ms
Memory	35.8 MB
Date	2022-01-19

Solution

public class Solution {
    public int Rob(int[] nums) {
        int n = nums.Length;
        if(n==1) return nums[0];
        return Math.Max(Recur(nums, 0, nums.Length-2), Recur(nums, 1, nums.Length-1));
}


public int Recur(int[] nums, int lo, int hi)
{
    int n = nums.Length;
    int prev = 0, cur = nums[lo];
    for (int i = lo+1; i <= hi; i++)
    {
        int temp = Math.Max(nums[i] + prev, cur);
        prev = cur;
        cur = temp;
    }
    return cur;
}
}

---

Complexity Analysis

Approach	Time	Space
Dynamic Programming	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Define the DP state clearly. Ask: "What is the minimum information I need to make a decision at each step?"
• Consider if you can reduce space by only keeping the last row/few values.
• LeetCode provides 1 hint(s) for this problem — try solving without them first.

💡 Hints

Hint 1: Since House[1] and House[n] are adjacent, they cannot be robbed together. Therefore, the problem becomes to rob either House[1]-House[n-1] or House[2]-House[n], depending on which choice offers more money. Now the problem has degenerated to the House Robber, which is already been solved.